package dfs_bfs;

import java.util.LinkedList;
import java.util.Queue;

public class lc695 {
    public static void main(String[] args) {
        System.out.println(maxAreaOfIsland(new char[][]{{'1','1','0','0','0'},{'1','1','0','0','0'},
                {'0','0','1','0','0'},{'0','0','0','1','1'}}));
    }
    public static int maxAreaOfIsland(char[][] grid) {
        //bfs
        int s = 0;
        int m = grid.length;
        int n = grid[0].length;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == '1'){
                    int t = dfs(grid, i, j);
                    s = Math.max(s, t);
                }
            }
        }
        return s;
    }
    public static int bfs(char[][] grid, int i, int j){
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{i, j});
        int s = 0;
        while( !queue.isEmpty()){
            int[] temp = queue.poll();
            if(temp[0] >= 0 && temp[1] >=0 && temp[0] < grid.length && temp[1] < grid[0].length && grid[temp[0]][temp[1]] == '1'){
                s++;
                grid[temp[0]][temp[1]] = '0';
                queue.add(new int[]{temp[0] - 1, temp[1]});
                queue.add(new int[]{temp[0] + 1, temp[1]});
                queue.add(new int[]{temp[0], temp[1] - 1});
                queue.add(new int[]{temp[0], temp[1] + 1});
            }
        }
        return s;
    }

    public static int dfs(char[][] grid, int i, int j) {
        if (i >= 0 && j >= 0 && i < grid.length && j < grid[0].length && grid[i][j] == '1') {
            grid[i][j] = '0';
            return 1 + dfs(grid, i + 1, j) + dfs(grid, i - 1, j) +
                    dfs(grid, i, j - 1) + dfs(grid, i, j + 1);
        }
        else return 0;
    }
}
